#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

typedef std::vector<int>    TVector;

void randomVector(TVector& v)
{
    size_t  size    =   random() % 100000;
    v.resize(size);
    for (size_t elNum = 0; elNum != size; ++elNum) {
        int element =   (random() % 10000) - 5000;
        v[elNum]    =   element;
    }
    std::sort(v.begin(), v.end());
}

void randomNUnionTask(std::vector<TVector>& src)
{
    size_t  size    =   random() % 1000;
    src.resize(size);
    for (size_t vectorNum = 0; vectorNum != size; ++vectorNum) {
        randomVector(src[vectorNum]);
    }

#ifdef NMERGE_PRINT_TESTCASE
    static const char           kPrefix[]   =   "std::vector<TVector> src = {";
    static const unsigned int   kPrefixLen  =   sizeof(kPrefix) - 1;
    std::cout << kPrefix;
    for (size_t vectorNum = 0; vectorNum != src.size(); ++vectorNum) {
        if (0 != vectorNum) {
            std::cout << "," << std::endl;
            for (unsigned int charNum = 0; charNum != kPrefixLen; ++charNum) {
                std::cout << " ";
            }
        }
        const TVector&  v(src[vectorNum]);
        std::cout << " {";
        for (size_t elNum = 0; elNum != v.size(); ++elNum) {
            if (0 != elNum) {
                std::cout << ", ";
            }
            std::cout << v[elNum];
        }
        std::cout  << " }";
    }
    std::cout << " };" << std::endl;
#endif
}

struct TRange {
    TRange(const TVector& v)
    : Begin(v.begin())
    , End(v.end())
    {}

    TVector::const_iterator Begin;
    TVector::const_iterator End;
};

bool isEmpty(const TRange& r)
{
    return r.Begin == r.End;
}

bool isRangeAfter(const TRange& r, const TRange& l)
{
    return *r.Begin > *l.Begin;
}

void nunion(const std::vector<TVector>& src, TVector& result)
{
    result.clear();
    size_t  expectedSize    =   0;
    for (size_t vectorNum = 0; vectorNum != src.size(); ++vectorNum) {
        expectedSize    +=  src[vectorNum].size();
    }
    result.reserve(expectedSize);


    typedef std::vector<TRange> TWorkFront;
    TWorkFront  workFront;
    workFront.reserve(src.size());
    for (size_t vecNum = 0; vecNum != src.size(); ++vecNum) {
        workFront.push_back(TRange(src[vecNum]));
    }

    workFront.erase( std::remove_if(workFront.begin(), workFront.end(), isEmpty)
                   , workFront.end() );
    std::sort(workFront.begin(), workFront.end(), isRangeAfter);

    while (false == workFront.empty()) {

        if (1 == workFront.size()) {
            const TRange&   lastOne(workFront.front());
            result.insert(result.end(), lastOne.Begin, lastOne.End);
            workFront.clear();
            continue;
        }

        TRange          current =   workFront.back();
        workFront.pop_back();
        const TRange&   next(workFront.back());
        int             limit(*next.Begin);

        TVector::const_iterator postUntil   =   std::upper_bound( current.Begin
                                                                , current.End
                                                                , limit );
        result.insert(result.end(), current.Begin, postUntil);
        current.Begin   =   postUntil;

        if (current.Begin == current.End) {
            continue;
        }

        TWorkFront::iterator    posForCurrent   =   std::lower_bound( workFront.begin()
                                                                    , workFront.end()
                                                                    , current
                                                                    , isRangeAfter );

        workFront.insert(posForCurrent, current);
    }
}

bool testNUnion()
{
    std::vector<TVector>    src;
    randomNUnionTask(src);

    TVector expected;
    size_t  expectedSize    =   0;
    for (size_t vectorNum = 0; vectorNum != src.size(); ++vectorNum) {
        expectedSize    +=  src[vectorNum].size();
    }
    expected.reserve(expectedSize);
    for (size_t vectorNum = 0; vectorNum != src.size(); ++vectorNum) {
        const TVector& vec(src[vectorNum]);
        expected.insert(expected.end(), vec.begin(), vec.end());
    }
    std::sort(expected.begin(), expected.end());

    TVector result;
    nunion(src, result);

    bool    isTestOk    =   result == expected;

    return isTestOk;
}


int main(int argC, char**argV)
{
    srand(time(NULL));

    if (false == testNUnion()) {
        std::cerr << "Test failed" << std::endl;
        return 1;
    }

    return 0;
}
